package leetcode.D600.T540;

class Solution {
//    public int singleNonDuplicate(int[] nums) {
//        int left = 0, right = nums.length-1;
//        while(left < right) {
//            int mid = left + (right - left) / 2;
//            if(nums[mid] != nums[mid-1] && nums[mid] != nums[mid+1]) {
//                return nums[mid];
//            }
//            if((mid-left) % 2 == 0) {
//                if(nums[mid] == nums[mid-1]) {
//                    right = mid - 2;
//                } else {
//                    left = mid + 2;
//                }
//            } else {
//                if(nums[mid] == nums[mid-1]) {
//                    left = mid + 1;
//                } else {
//                    right = mid - 1;
//                }
//            }
//        }
//        return nums[left];
//    }

    // 二刷
    public int singleNonDuplicate(int[] nums) {
        int left = 0, right = nums.length-1;// 偶数
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(mid % 2 > 0) {
                if(nums[mid-1] == nums[mid]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else {
                if(mid == nums.length-1) {
                    return nums[mid];
                } else if(nums[mid] == nums[mid+1]) {
                    left = mid + 2;
                } else {
                    right = mid;
                }
            }
        }
        return nums[left];
    }
}